做的时候觉得如果要查看两个数的乘积是不是平方数,就必须把每个数字与另外的每一个数字比较,也就是有O(N^2)的复杂度。谁知道一看题解,竟然用到了数学的知识。每一个平方数都可以表示成为多个素数的偶次幂的乘积。这个其实是应用了唯一分解定理。唯一分解定理是说:任何大于1的自然数都可以唯一的用若干个素数的乘积表示出来。那么一个平方数自然就可以表示成为若干个素数的偶次幂的乘积了。然后我们就可以运用这个做题了。把每个数字化简到最简的数字,然后就可以得到答案了。
1 |
|
云腾致雨,露结为霜
做的时候觉得如果要查看两个数的乘积是不是平方数,就必须把每个数字与另外的每一个数字比较,也就是有O(N^2)的复杂度。谁知道一看题解,竟然用到了数学的知识。每一个平方数都可以表示成为多个素数的偶次幂的乘积。这个其实是应用了唯一分解定理。唯一分解定理是说:任何大于1的自然数都可以唯一的用若干个素数的乘积表示出来。那么一个平方数自然就可以表示成为若干个素数的偶次幂的乘积了。然后我们就可以运用这个做题了。把每个数字化简到最简的数字,然后就可以得到答案了。
1 | #include <iostream> |